/*

 * To change this template, choose Tools | Templates

 * and open the template in the editor.

 */
package grafos_nac20;

import excecoes.ArquivoInexistenteException;
import java.io.BufferedReader;
import java.util.Stack;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 *
 *
@author fillipe
 */
public class Grafo {

    private Map<Aluno, List<String>> tabela;
    private Stack<Aluno> pilha;
    private List<List<String>> caminhos;
    private Set<Aluno> amigos;
    private String rmRaiz;
    private String diretorio;
    private int pnum;

    public Grafo(String rmRaiz) {
        tabela = new HashMap<Aluno, List<String>>();
        pilha = new Stack<Aluno>();
        caminhos = new ArrayList<List<String>>();
        pnum = 0;
        this.rmRaiz = rmRaiz;
        diretorio = "rede";
    }

    public void montaTabela() {
        File file = new File(diretorio);
        File[] fileList = file.listFiles();
        try {
            for (File f : fileList) {
                String fileName = f.getName();
                if (!fileName.endsWith(".txt")) {
                    continue;
                }

                File arq = new File(diretorio, fileName);
                BufferedReader br = new BufferedReader(new FileReader(arq));
                String rmInterno = "";
                List<String> colunas = new ArrayList<String>();
                while ((rmInterno = br.readLine()) != null) {
                    if (!rmInterno.equals("")) {
                        colunas.add(rmInterno);
                    }
                }
                //String rm = fileName.replace(".txt", ""); //para versao de teste
                String rm = fileName.replace(".txt", "").substring(2); //para valer
                Aluno aluno = new Aluno(rm, false);
                tabela.put(aluno, colunas);
            }
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

    public void percorrerPorProfundidade(String rm) throws ArquivoInexistenteException {
        arvoreProfundidade(rm);
        pnum = 0;
    }

    private void arvoreProfundidade(String rm) throws ArquivoInexistenteException {
        Aluno noCorrente = buscaAluno(rm);
        noCorrente.setVisitado(true);
        pnum++;
        noCorrente.setNum(pnum);
        noCorrente.setLow(pnum);
        List<String> listaVizinhos = tabela.get(noCorrente);
        for (String rmVizinho : listaVizinhos) {
            Aluno noVizinho = buscaAluno(rmVizinho);
            if (!noVizinho.isVisitado()) {
                noVizinho.setNoPai(noCorrente);
                arvoreProfundidade(noVizinho.getRm());
                if (noVizinho.getLow() >= noCorrente.getNum()) {
                    noCorrente.setArticulacao(true);
                    noCorrente.setRm(noCorrente.getRm());
                }
                if (noVizinho.getLow() < noCorrente.getLow()) {
                    noCorrente.setLow(noVizinho.getLow());
                }
            } else {
                if (noCorrente.getNoPai() != null && noVizinho.getNoPai() != null) {
                    if (!noVizinho.getNoPai().equals(noCorrente.getNoPai())) {
                        if (noVizinho.getNum() < noCorrente.getLow()) {
                            noCorrente.setLow(noVizinho.getNum());
                        }
                    }
                }
            }
        }
    }

    public String percorrerPorNivel(String rm) throws ArquivoInexistenteException {
        for (Aluno aluno : tabela.keySet()) {
            aluno.setVisitado(false);
        }
        Aluno aluno = buscaAluno(rm);
        aluno.setNivel(0);
        aluno.setVisitado(true);
        arvoreNiveis(aluno);
        String ret = "";
        List<Aluno> alunos = new ArrayList<Aluno>(tabela.keySet());
        Collections.sort(alunos, new Comparator<Aluno>() {

            @Override
            public int compare(Aluno o1, Aluno o2) {
                if (o1.getNivel() > o2.getNivel()) {
                    return 1;
                } else if (o1.getNivel() < o2.getNivel()) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        for (Aluno a : alunos) {
            if (a.isVisitado()) {
                ret += "RM: " + a.getRm() + "\tNivel: " + a.getNivel() + "\n";
            }
        }
        ret += "\n\nNao contatados:\n";
        for(Aluno a : alunos){
            if(!a.isVisitado()){
                ret += "RM: " + a.getRm() + "\tNivel: " + a.getNivel() + "\n";
            }                
        }

        return ret;
    }

    private void arvoreNiveis(Aluno aluno) throws ArquivoInexistenteException {
        List<Aluno> vizinhos = buscaVizinhos(aluno);
        for (Aluno a : vizinhos) {
            if (!a.isVisitado()) {
                a.setVisitado(true);
                a.setNivel(aluno.getNivel() + 1);
                arvoreNiveis(a);
            }
        }
    }

    public List<List<String>> getCaminhos() {
        List<Aluno> listaFolhas = buscaFolhas();
        for (Aluno aluno : listaFolhas) {
            List<String> caminho = new ArrayList<String>();
            montaCaminho(aluno);
            while (!pilha.empty()) {
                caminho.add(pilha.pop().getRm());
            }
            caminhos.add(caminho);
        }
        return caminhos;
    }

    private void montaCaminho(Aluno aluno) {
        if (pilha.empty()) {
            pilha.push(aluno);
        }
        if (aluno.getNoPai() != null) {
            pilha.push(aluno.getNoPai());
            montaCaminho(aluno.getNoPai());
        }
    }

    private List<Aluno> buscaFolhas() {
        List<Aluno> listaFolhas = new ArrayList<Aluno>();
        for (Aluno aluno : tabela.keySet()) {
            if (aluno.getNoPai() != null) {
                boolean folha = true;
                for (Aluno a : tabela.keySet()) {
                    if (a.getNoPai() != null && a.getNoPai().getRm().equals(aluno.getRm())) {
                        folha = false;
                        break;
                    }
                }
                if (folha) {
                    listaFolhas.add(aluno);
                }
            }
        }
        return listaFolhas;
    }

    private Aluno buscaAluno(String rm) throws ArquivoInexistenteException {
        for (Aluno aluno : tabela.keySet()) {
            if (aluno.getRm().trim().equals(rm.trim())) {
                return aluno;
            }
        }
        throw new ArquivoInexistenteException("Nao existe um arquivo com o RM " + rm);
    }

    private List<Aluno> buscaVizinhos(Aluno aluno) throws ArquivoInexistenteException {
        List<String> listaRms = tabela.get(aluno);
        List<Aluno> listaVizinhos = new ArrayList<Aluno>();
        for (String rm : listaRms) {
            listaVizinhos.add(buscaAluno(rm));
        }
        return listaVizinhos;
    }

    public void imprimeNosEncontrados() {
        int cont = 1;
        for (Aluno aluno : tabela.keySet()) {
            String rmPai = "";
            if (aluno.getNoPai() == null) {
                if (aluno.getRm().equals(rmRaiz)) {
                    rmPai = "NAO POSSUI PAI POIS EH NO RAIZ";
                } else {
                    rmPai = "NAO POSSUI, NO NAO CONTATADO";
                }
            } else {
                rmPai = aluno.getNoPai().getRm();
            }
            String artic = aluno.isArticulacao() ? "true" : "\t";
            //if(aluno.getNoPai() != null && aluno.getNoPai().getRm().equals("INSIRA O RM AKI"))
            System.out.println(cont + " rm:" + aluno.getRm() + "    visitado:" + aluno.isVisitado() + "     articulacao:" + artic + "     pai:" + rmPai);
            cont++;
        }
    }
}